package arithmetic.demo4;

import java.util.ArrayList;
import java.util.*;
import java.util.List;


/**
 * 题目： floodfill算法_太平洋大西洋水流问题
 */

class Solution {

    // 方位
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};

    // 创建两个布尔数组来确定太平洋和大西洋的流向
    boolean[][]  pacificPath;
    boolean[][]  atlanticPath;

    // 长和宽
    int row , col;
    
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // 初始化
        row = heights.length;
        col = heights[0].length;

        pacificPath = new boolean[row][col];
        atlanticPath =  new boolean[row][col];

        
        for(int i = 0; i< row ; i++)  {
            // 左边
                if(!pacificPath[i][0]) {
                    pacificPath[i][0] = true;
                    dfs(heights, i, 0);
                }

                // 右边
                if(!atlanticPath[i][col-1]) {
                    atlanticPath[i][col-1] = true;
                    bfs(heights, i, col-1);
                }
        }

        for(int j = 0; j<col; j++) {
            // 上面
            if(!pacificPath[0][j]) {
                pacificPath[0][j] = true;
                dfs(heights, 0, j);
            }

            // 下面
            if(!atlanticPath[row-1][j]) {
                atlanticPath[row-1][j] = true;
                bfs(heights,row-1, j);
            }
        }


    // 实例化返回结果
    List<List<Integer>> ret = new ArrayList<>();

    for(int i =0; i<row ; i++) {
        for(int j = 0; j<col; j++) {

            // 同时被太平洋和大西洋流过的加入下标
            if(pacificPath[i][j] && atlanticPath[i][j]) {
                List<Integer> flg = new ArrayList<>();
                flg.add(i);
                flg.add(j);
                ret.add(flg);
            }
        }
    }

    return ret;
    }

    private void dfs(int[][] heights, int index, int pos) {
        
        // 方位移动
        for(int k =0 ; k<4; k++) {
                int i = index + dx[k];
                int j = pos + dy[k];

                // 剪枝
                if(i >= 0 && i < row 
                && j >= 0  && j < col 
                && !pacificPath[i][j] && heights[i][j] >= heights[index][pos]) {

                    // 标记
                    pacificPath[i][j] = true;
                    // 深搜
                    dfs(heights,i, j);
                }
        }
    }

    private void bfs(int[][] heights, int index, int pos) {
        
        for(int k =0 ; k<4; k++) {
                int i = index + dx[k];
                int j = pos + dy[k];
                if(i >= 0 && i < row 
                && j >= 0  && j < col 
                && !atlanticPath[i][j] && heights[i][j] >= heights[index][pos]) {
                    atlanticPath[i][j] = true;
                    bfs(heights,i, j);
                }
        }
    }

}




class Solution2 {

    // 方位
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};

    // 长和宽
    int row ,col;

    // 结果数组
    char[][] ret ;
    char[][] tmp;

    public char[][] updateBoard(char[][] board, int[] click) {
        // 起始位置
        row = board.length;
        col = board[0].length;
        int  r = click[0], c = click[1];
        ret = new char[row][col];
        tmp = new char[row+1][col+1];



        // 开始拷贝
        for(int i = 0; i <row ; i++) {

            for(int j = 0;j < col ; j++) {

                ret[i][j] = tmp[i+1][j+1] = board[i][j];
            }
        }

        // 遇到雷时
        if(board[r][c] == 'M') {
            ret[r][c] = 'X';
            return ret;
        }

        // 起始位置开始深搜
        dfs(tmp, r,c);

        return ret;

    }

    private void dfs( char[][] tmp ,int x, int y ) {
        int count = 0;

        // 统计当前环绕一周位置雷的个数
        for(int i = x -1; i <= x + 1; i++) {
            for(int j = y -1 ; j <= y + 1 ; j++) {
                if( tmp[i+1][j+1] == 'M') {
                    count++;
                }
            }
        }

        // 加入到当前位置
        if(count > 0) {
            ret[x][y] = (char)(count + '0');
        } else if(count == 0) {
            ret[x][y] = 'B';
        }


        for(int i =0; i < 4 ; i++) {
            int index = x + dx[i];
            int pos  = y + dy[i];

            if( index >= 0 && index < row
                    && pos >= 0 && pos < col
                    && ret[index][pos] == 'E') {
                dfs(tmp, index, pos);
            }

        }
    }


    public static void main(String[] args) {

        char[][] board = {{'E','E','E','E','E'},{'E','E','M','E','E'},{'E','E','E','E','E'},{'E','E','E','E','E'}};

        int[] click = {3,0};

        Solution2 solution2 = new Solution2();
        solution2.updateBoard(board,click);



    }
}


/**
 * 题目： foodFilled算法_扫雷游戏
 */

class Solution3 {

    // 方位
    int[] dx = {0,0,-1,1,-1,-1,1,1};
    int[] dy = {-1,1,0,0,-1,1,-1,1};

    // 长和宽
    int row ,col;

    // 结果数组
    char[][] ret ;

    public char[][] updateBoard(char[][] board, int[] click) {
        // 起始位置
        row = board.length;
        col = board[0].length;
        int  r = click[0], c = click[1];
        ret = new char[row][col];



        // 开始拷贝
        for(int i = 0; i <row ; i++) {

            for(int j = 0;j < col ; j++) {
                ret[i][j]  = board[i][j];
            }
        }

        // 遇到雷时
        if(board[r][c] == 'M') {
            ret[r][c] = 'X';
            return ret;
        }

        // 起始位置开始深搜
        dfs(board, r,c);

        return ret;

    }

    private void dfs( char[][] tmp ,int x, int y ) {
        int count = 0;

        // 统计当前环绕一周位置雷的个数
        for(int i = x -1; i <= x + 1; i++) {
            for(int j = y -1 ; j <= y + 1 ; j++) {
                if( i >= 0 && i < row && j >= 0 && j < col && tmp[i][j] == 'M') {
                    count++;
                }
            }
        }

        // 加入到当前位置
        if(count > 0) {
            ret[x][y] = (char)(count + '0');
            return;
        } else if(count == 0) {
            ret[x][y] = 'B';
        }


        for(int i =0; i < 8 ; i++) {
            int index = x + dx[i];
            int pos  = y + dy[i];

            if( index >= 0 && index < row
                    && pos >= 0 && pos < col
                    && ret[index][pos] == 'E') {
                dfs(tmp, index, pos);
            }

        }
    }
}

/**
 * 题目： 记忆化搜索_斐波那契数列
 */

class Solution4 {

    // 进行记忆化搜索的演示
    public int fib(int n) {
        // 初始化一个备忘录
        int[] nums = new int[31];
        Arrays.fill(nums,-1);
        return  dfs(n,nums);
    }

    private int dfs(int n , int[] nums) {
        // 初始结果放入备忘录
        if(n== 0 || n == 1) {
            nums[n] = n;
        }

        // 使用备忘录进行剪枝
        if(nums[n] != -1) {
            return nums[n];
        }




        // 计算结果到备忘录
        nums[n] = dfs(n-1,nums) + dfs(n-2 , nums);

        // 返回结果
        return  nums[n];
    }
}


/**
 * 题目： 记忆化搜索_不同路径
 */

class Solution5 {

    int row ,col;
    int[] dx = {0,1};
    int[] dy = {1,0};

    int[][] path;



    int ret ;
    public int uniquePaths(int m, int n) {
        // 初始化
        row = m;
        col = n;
        path = new int[m+1][n+1];

        // 全部填充为 -1
        for(int[]tmp : path) {
            Arrays.fill(tmp, -1);
        }

        return dfs(row,col);
    }

    private int dfs(int index, int pos) {
        // 遇到 边界直接返回
        if(index == 0 || pos == 0) {
            return 0;
        }

        // 一旦查找到最后一位就++ 返回
        if(index == 1 && pos == 1) {
            path[0][0] = 1;
            return 1;
        }

        // 遇到直接就返回
        if(path[index][pos] != -1) {
            return path[index][pos];
        }

        // 存储备忘录中
        path[index][pos] = dfs(index-1,pos) + dfs(index, pos-1);

        // 直接返回
        return path[index][pos];

    }
}


